package com.lw.leetcode.tree.b;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * Created with IntelliJ IDEA.
 * 823. 带因子的二叉树
 *
 * @author liw
 * @version 1.0
 * @date 2021/7/21 13:18
 */
public class NumFactoredBinaryTrees {

    public static void main(String[] args) {
        NumFactoredBinaryTrees test = new NumFactoredBinaryTrees();
        int length = 20;

        Map<Integer, Integer> map = new HashMap<>();
        int[] ar = new int[length];
        for (int i = 0; i < length; i++) {
            int value = (int) (Math.random() * 100 + 2);
            if (map.get(value) != null) {
                while (map.get(value) != null) {
                    value = (int) (Math.random() * 100 + 2);
                }
            }
            ar[i] = value;
            map.put(value, 1);
        }

//        System.out.println(Arrays.toString(ar));
        int[] arr = {2, 4, 8, 16, 32};
//        int[] arr = {18,3,6,2};
        int i = test.numFactoredBinaryTrees(arr);
        System.out.println(i);
    }

    public int numFactoredBinaryTrees(int[] arr) {
        int length = arr.length;
        int m = 1000000007;
        Map<Integer, Integer> map = new HashMap<>(length << 1);
        long[] counts = new long[length];
        Arrays.sort(arr);
        for (int i = 0; i < length; i++) {
            map.put(arr[i], i);
        }
        Arrays.fill(counts, 1);
        Integer value;
        int item;
        for (int i = 1; i < length; i++) {
            int key = arr[i];
            int pow = (int) Math.pow(key, 0.5);
            if (pow * pow == key && (value = map.get(pow)) != null) {
                counts[i] += counts[value] * counts[value];
                pow--;
            }
            for (int j = 0; (item = arr[j]) <= pow; j++) {
                if (key % item == 0 && (value = map.get(key / item)) != null) {
                    counts[i] += ((counts[j] * counts[value]) << 1);
                }
            }
        }
        long count = 0;
        for (long i : counts) {
            count += i;
        }
        return (int) (count % m);
    }
}
